package leetcode.tree_problem;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 958. 二叉树的完全性检验
 * https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree/
 */
public class IsCompleteTree {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null){
            return true;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        boolean stateTransition = true;
        //句意很重要题目所需的理解是求这颗树是否满足完全二叉树
        deque.offer(root);
        while (!deque.isEmpty()){
            TreeNode curNode = deque.poll();
            if (stateTransition){

                if (curNode.left != null && curNode.right != null){
                    deque.offer(curNode.left);
                    deque.offer(curNode.right);
                }else if (curNode.left != null){
                    deque.offer(curNode.left);
                    stateTransition = false;
                }else if (curNode.right != null){
                    return false;
                }
                //这些情况考虑完还没有考虑遇到第一个叶子节点else既是
                else {
                    stateTransition = false;
                }
            }else {
                //如果走到这说明已转换至状态二，一定注意状态二是叶子节点，左数和又树都是空不是当前树为空
                if (curNode.left != null || curNode.right != null){
                    return false;
                }
            }


        }

        return true;
    }
}
